package oj;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author 郝文雪
 * @date 2022/8/27 10:45
 * @Description Test
 */
public class LC210 {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        if(numCourses==0) return new int[0];
        int[] indegrees=new int[numCourses];//存储入度
        Queue<Integer> q=new LinkedList<>();
        for(int[] p:prerequisites){
            indegrees[p[0]]++;
        }
        for(int i=0;i<numCourses;i++){
            if(indegrees[i]==0){
                q.offer(i);
            }
        }
        int count=0;//可以完成的课程数量
        int[] res=new int[numCourses];
        while(!q.isEmpty()){
            int cur=q.poll();
            res[count++]=cur;
            for(int[] p:prerequisites){
                if(p[1]==cur){
                    indegrees[p[0]]--;
                    if(indegrees[p[0]]==0){
                        q.offer(p[0]);
                    }
                }
            }
        }
        if(count==numCourses){
            return res;
        }
        return new int[0];
    }
}
